package com.origin.niuke.binarySearch;

/**
 * NC71 旋转数组的最小数字
 * 算法：二分查找
 * 数组旋转一次后, 第一个元素肯定比最后一个元素大, 最小的数的前边是递增的, 最小数后面的数也是递增的
 * 1、array[mid] > array[r], 说明 mid 在第一段的递增数字上, l 要往后移
 * 2、array[mid] = array[r], 因为数组中的数字可以重复, 类似 [1,0,1,1,1] 或者[1,1,1,0,1] 所以不好判断 mid 在哪一段, 只能一个一个试
 * 3、array[mid] < array[r], 最小的数一定在 mid 的左边
 *
 * @author yezh
 * @version 1.0
 * @date 2022/11/7 22:36
 */
public class NC71 {

    public int minNumberInRotateArray(int[] array) {
        int l = 0, r = array.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (array[mid] > array[r]) l = mid + 1;
            else if (array[mid] == array[r]) r = r - 1;
            else r = mid;
        }
        return array[l];
    }

}
